import java.util.*;

//为高尔夫比赛砍树
//测试链接：https://leetcode.cn/problems/cut-off-trees-for-golf-event/description/
public class CutOffTree {
    int m, n;

    public int cutOffTree(List<List<Integer>> f) {
        m = f.size();
        n = f.get(0).size();
        List<int[]> trees = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (f.get(i).get(j) > 1)
                    trees.add(new int[] { i, j });
        Collections.sort(trees, (a, b) -> {
            return f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
        });
        int bx = 0, by = 0;
        int ret = 0;
        for (int[] next : trees) {
            int a = next[0], b = next[1];
            int step = bfs(f, bx, by, a, b);
            if (step == -1)
                return -1;
            ret += step;
            bx = a;
            by = b;
        }
        return ret;
    }

    int[] dx = { 0, 0, 1, -1 };
    int[] dy = { 1, -1, 0, 0 };

    public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey) {
        if (bx == ex && by == ey)
            return 0;
        Queue<int[]> q = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        q.add(new int[] { bx, by });
        vis[bx][by] = true;
        int step = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            step++;
            while (sz-- != 0) {
                int[] t = q.poll();
                int a = t[0], b = t[1];
                for (int i = 0; i < 4; i++) {
                    int x = a + dx[i], y = b + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && f.get(x).get(y) != 0 && !vis[x][y]) {
                        if (x == ex && y == ey)
                            return step;
                        q.add(new int[] { x, y });
                        vis[x][y] = true;
                    }
                }
            }

        }
        return -1;
    }
}
